#ifndef _TREENODE_H_
#define _TREENODE_H_

/*****************************************************************************/
/**********				_TreeNode class declaration					**********/
/*****************************************************************************/
//Encapsulates data and functionality of an AVL tree node

#include <cstring>
#include "Common.h"
#include "Exceptions.h"
#include <cassert>

namespace DataStructuresWet1
{

template <typename DataT>
class _TreeNode
{
/*************************************************/
/**********			Public members			******/
/*************************************************/
public:
	//types
	//Type of parents for a tree node
	typedef enum
	{
		IS_LEFT_CHILD		= 0,
		IS_RIGHT_CHILD		= 1,
		IS_ORPHAN			= 2
	}TreeNodeParentage;

	//types of children for a tree node
	typedef enum
	{
		LEAF				= 0,
		HAS_LEFT_CHILD		= 1,
		HAS_RIGHT_CHILD		= 2,
		HAS_TWO_CHILDREN	= 3
	}TreeNodeChildrenType;

	//Ctor
	_TreeNode									(DataT*				dataPtr, 
												_TreeNode<DataT>*	parent			= NULL, 
												_TreeNode<DataT>*	leftChild		= NULL, 
												_TreeNode<DataT>*	rightChild		= NULL);
	//Copy ctor
	_TreeNode									(const _TreeNode& other);
	//Gets the type of parent for tree node
	TreeNodeParentage		NodeParentage		() const;
	//Gets the type of children the tree node has
	TreeNodeChildrenType	NodeChildrenType	() const;
	//Gets the parent node of the tree node, NULL if none
	_TreeNode<DataT>*		GetParent			() const;
	//Get left child of node, NULL if none
	_TreeNode<DataT>*		GetLeftChild		() const;
	//Get right child of node, NULL if none
	_TreeNode<DataT>*		GetRightChild		() const;
	//Get left sibling of node,, NULL if none
	_TreeNode<DataT>*		GetLeftSibling		() const;
	//Get right sibling of node,, NULL if none
	_TreeNode<DataT>*		GetRightSibling		() const;
	//Get the data of the current node
	DataT* const			GetDataPtr			() const;
	//Get size of the sub-tree of which the current node is the root of
	int						GetSize				() const;
	//Get size of left-sub tree
	int						GetWeight			() const;
	//Get height of the sub-tree of which the current node is the root of
	int						GetHeight			() const;
	//Get balance factor of current tree node
	int						GetBalanceFactor	() const;
	//Switch data of 2 tree nodes
	void					SwitchPosition		(_TreeNode<DataT>& other);
	//Replace the current tree node with it's parent. The parent is left
	// as orphan
	void					ReplaceParent		();
	//Make the node orphan
	void					MakeOrphan			();
	//Setter for left child
	void					SetLeftChild		(_TreeNode<DataT>*	value);
	//Setter for right child
	void					SetRightChild		(_TreeNode<DataT>*	value);
	//Setter for the data pointer
	void					SetDataPtr			(DataT*				value);
	//Returns left most child of node. If none, then returns the node itself
	_TreeNode<DataT>*		GetLeftMostChild	() const;
	//Returns right most child of node. If none, then returns the node itself
	_TreeNode<DataT>*		GetRightMostChild	() const;
	//Rotate Right Right
	void					RotateRR			();
	//Rotate Right Left
	void					RotateRL			();
	//Roate Left Left
	void					RotateLL			();
	//Rotate Left Right
	void					RotateLR			();
	//Update node size
	void					UpdateSize			();
	//Update Node Height
	void					UpdateHeight		();
/*************************************************/
/**********		Protected members			******/
/*************************************************/
protected:
	//Basic rotations:
	//Left
	void					RotateLeft			();
	//Right
	void					RotateRight			();
	//Data members
	_TreeNode<DataT>*		Parent;
	_TreeNode<DataT>*		LeftChild;
	_TreeNode<DataT>*		RightChild;
	DataT*					DataPtr;
	int						Size;
	int						Height;
	//int						Weight;
};

//_TreeNode Implementation
template <typename DataT>
_TreeNode<DataT>::_TreeNode(
	DataT*				dataPtr, 
	_TreeNode<DataT>*	parent, 
	_TreeNode<DataT>*	leftChild, 
	_TreeNode<DataT>*	rightChild) : 
	Parent(parent), 
	LeftChild(leftChild), 
	RightChild(rightChild),
	DataPtr(dataPtr)
{
	UpdateSize();
	UpdateHeight();
}

template <typename DataT>
_TreeNode<DataT>::_TreeNode(const _TreeNode& other) : 
	Parent(other.Parent), 
	LeftChild(other.LeftChild), 
	RightChild(other.RightChild),
	DataPtr(other.DataPtr),
	Size(other.Size),
	Height(other.Height) {}

template <typename DataT>
typename _TreeNode<DataT>::TreeNodeParentage _TreeNode<DataT>::NodeParentage()  const
{
	if (!this->Parent)
	{
		return IS_ORPHAN;
	}
	if (this->Parent->LeftChild == this)
	{
		return IS_LEFT_CHILD;
	}
	assert(this->Parent->RightChild == this);
	return IS_RIGHT_CHILD;
}

template <typename DataT>
typename _TreeNode<DataT>::TreeNodeChildrenType _TreeNode<DataT>::NodeChildrenType()  const
{
	if (!this->LeftChild && !this->RightChild)
	{
		return LEAF;
	}
	if (this->LeftChild != NULL && this->RightChild != NULL)
	{
		return HAS_TWO_CHILDREN;
	}
	if (this->LeftChild)
	{
		return HAS_LEFT_CHILD;
	}
	return HAS_RIGHT_CHILD;
}

template <typename DataT>
_TreeNode<DataT>*	_TreeNode<DataT>::GetParent			()  const
{
	return this->Parent;
}

template <typename DataT>
_TreeNode<DataT>*	_TreeNode<DataT>::GetLeftChild		()  const
{
	return this->LeftChild;
}

template <typename DataT>
_TreeNode<DataT>*	_TreeNode<DataT>::GetRightChild		()  const
{
	return this->RightChild;
}

template <typename DataT>
_TreeNode<DataT>*	_TreeNode<DataT>::GetLeftSibling		()  const
{
	if (this->Parent == NULL)
	{
		//if orphan, return NULL
		return NULL;
	}
	else
	{
		return this->Parent->LeftSibling;
	}
}

template <typename DataT>
_TreeNode<DataT>*	_TreeNode<DataT>::GetRightSibling	()  const
{
	if (this->Parent == NULL)
	{
		//if orphan, return NULL
		return NULL;
	}
	else
	{
		return this->Parent->RightSibling;
	}
}

template <typename DataT>
DataT* const		_TreeNode<DataT>::GetDataPtr			() const
{
	return this->DataPtr;
}

template <typename DataT>
int				_TreeNode<DataT>::GetSize					() const
{
	return this->Size;
}

template <typename DataT>
void			_TreeNode<DataT>::SetLeftChild		(_TreeNode<DataT>* value)
{
	this->LeftChild = value;
	if (value != NULL)
	{
		value->Parent = this;
	}
	//Update size and height
	this->UpdateSize();
	this->UpdateHeight();
}

template <typename DataT>
void			_TreeNode<DataT>::SetRightChild		(_TreeNode<DataT>* value)
{
	this->RightChild = value;
	if (value != NULL)
	{
		value->Parent = this;
	}
	//Update size and height
	this->UpdateSize();
	this->UpdateHeight();
}

template <typename DataT>
_TreeNode<DataT>*		_TreeNode<DataT>::GetLeftMostChild	() const
{
	_TreeNode<DataT>* node = const_cast<_TreeNode<DataT>*> (this); //this is okay, since we are not changing the state of this
	while(node->GetLeftChild() != NULL)
	{
		node = node->GetLeftChild();
	}
	return node;
}
template <typename DataT>
_TreeNode<DataT>*		_TreeNode<DataT>::GetRightMostChild	() const
{
	_TreeNode<DataT>* node = const_cast<_TreeNode<DataT>*> (this); //this is okay, since we are not changing the state of this
	while(node->GetRightChild() != NULL)
	{
		node = node->GetRightChild();
	}
	return node;
}

template <typename DataT>
void					_TreeNode<DataT>::RotateLeft		()
{
	_TreeNode<DataT>* tmp = this->RightChild;
	//Set right child to be left sub-tree of right child
	this->SetRightChild(tmp->GetLeftChild());
	//Replace current node with right child
	switch (this->NodeParentage())
	{
	case IS_LEFT_CHILD:
		this->Parent->SetLeftChild(tmp);
		break;
	case IS_RIGHT_CHILD:
		this->Parent->SetRightChild(tmp);
		break;
	case IS_ORPHAN:
		tmp->Parent = NULL;
		break;
	}
	//Set current node as left child of previous right child
	tmp->SetLeftChild(this);

}
template <typename DataT>
void					_TreeNode<DataT>::RotateRight		()
{
	_TreeNode<DataT>* tmp = this->LeftChild;
	//Set left child to be right sub-tree of left child
	this->SetLeftChild(tmp->GetRightChild());
	//Replace current node with left child
	switch (this->NodeParentage())
	{
	case IS_LEFT_CHILD:
		this->Parent->SetLeftChild(tmp);
		break;
	case IS_RIGHT_CHILD:
		this->Parent->SetRightChild(tmp);
		break;
	case IS_ORPHAN:
		tmp->Parent = NULL;
		break;
	}
	//Set current node as right child of previous left child
	tmp->SetRightChild(this);
}

template <typename DataT>
void					_TreeNode<DataT>::UpdateSize			()
{
	int leftChildSize = (this->LeftChild != NULL) ? this->LeftChild->GetSize() : 0;
	int rightChildSize = (this->RightChild != NULL) ? this->RightChild->GetSize() : 0;
	this->Size = leftChildSize + rightChildSize + 1;
}

template <typename DataT>
void					_TreeNode<DataT>::MakeOrphan			()
{
	switch (this->NodeParentage())
	{
	case IS_LEFT_CHILD:
		this->Parent->SetLeftChild(NULL);
		break;
	case IS_RIGHT_CHILD:
		this->Parent->SetRightChild(NULL);
		break;
	case IS_ORPHAN:
		//do nothing
		break;
	}
	this->Parent = NULL;
}

template <typename DataT>
void					_TreeNode<DataT>::RotateRR			()
{
	//Just a left rotation of current node
	this->RotateLeft();
}
template <typename DataT>
void					_TreeNode<DataT>::RotateRL			()
{
	//Right rotation of right child
	this->RightChild->RotateRight();
	//Followed by a left rotation of this node
	this->RotateLeft();
}
template <typename DataT>
void					_TreeNode<DataT>::RotateLL			()
{
	//Just a right rotation of current node
	this->RotateRight();
}
template <typename DataT>
void					_TreeNode<DataT>::RotateLR			()
{
	//Left rotation of Left child
	this->LeftChild->RotateLeft();
	//Followed by a right rotation of this node
	this->RotateRight();
}

template <typename DataT>
void					_TreeNode<DataT>::UpdateHeight		()
{
	int leftChildHeight = (this->LeftChild != NULL) ? this->LeftChild->GetHeight() : 0;
	int rightChildHeight = (this->RightChild != NULL) ? this->RightChild->GetHeight() : 0;
	this->Height = MAX(leftChildHeight, rightChildHeight) + 1;
}

template <typename DataT>
int						_TreeNode<DataT>::GetHeight			() const
{
	return this->Height;
}

template <typename DataT>
int						_TreeNode<DataT>::GetWeight			() const
{
	return (this->LeftChild != NULL) ? this->LeftChild->Size : 0;
}

template <typename DataT>
int						_TreeNode<DataT>::GetBalanceFactor	() const
{
	int leftChildHeight = (this->LeftChild != NULL) ? this->LeftChild->GetHeight() : 0;
	int rightChildHeight = (this->RightChild != NULL) ? this->RightChild->GetHeight() : 0;
	return  leftChildHeight - rightChildHeight;
}

template <typename DataT>
void					_TreeNode<DataT>::SwitchPosition		(_TreeNode<DataT>& other)
{
	DataT* tmp = other.DataPtr;
	other.DataPtr = this->DataPtr;
	this->DataPtr = tmp;
}

template <typename DataT>
void					_TreeNode<DataT>::ReplaceParent			()
{
	_TreeNode<DataT>* parent = this->Parent;
	//parent should no longer point to this node
	switch(this->NodeParentage())
	{
	case IS_LEFT_CHILD:
		parent->LeftChild = NULL;
		break;
	case IS_RIGHT_CHILD:
		parent->RightChild = NULL;
		break;
	case IS_ORPHAN:
		return;
		break;
	}

	//Set "grandparent" to be parent
	switch(this->Parent->NodeParentage())
	{
	case IS_LEFT_CHILD:
		parent->Parent->SetLeftChild(this);
		break;
	case IS_RIGHT_CHILD:
		parent->Parent->SetRightChild(this);
		break;
	case IS_ORPHAN:
		this->Parent = NULL;
		break;
	}
	//Make previous parent orphan
	parent->Parent = NULL;
}

template <typename DataT>
void				_TreeNode<DataT>::SetDataPtr				(DataT* value)
{
	this->DataPtr = value;
}

}//DataStructuresWet1
#endif //_TREENODE_H_
